#! /usr/bin/python

import math
import time

now = time.time()

def isPrime(n):
    if n ==2 or n==3 or n==5 or n==7: return True
    if n == 1 or n%2 == 0 or n%3 == 0: return False
    for i in range(5, int(math.sqrt(n)+1), 6):
	if n%i == 0 or n%(i+2) == 0: 
	   #print i
	   return False
    return True

#print isPrime(1306133)

#def gcd(a, b):
    
nlist = [0 for i in range(10**7)]
primes = [2]

nlist = [0]*10**7
nlist[0] = 0
nlist[1] = 1
nlist[2] = 2
p = 4
power = 2
while(p < 10**7):
     nlist[p] = power + 1
     power += 1
     p *= 2

for i in range(1, int(math.sqrt(10**7)+1), 2):
    if isPrime(i): 
	primes.append(i)
	power = 2
	p = i**2
	while(p < 10**7):
	     nlist[p] = power+1
	     power += 1
	     p *= i

num = 0
for i in range(3, 10**7):
    for p in primes:
	if i == p: continue	
	index = i * p
	if index >= 10**7: break
	if nlist[index] != 0: continue
	if i%p == 0:
	   r = i 
	   while(r%p == 0): r /= p
	   nlist[index] = nlist[i] + nlist[r]
	else: 
	   if nlist[i] != 0: nlist[index] = nlist[i]*2
	   elif isPrime(i): nlist[index] = 4
	   
	#print index

#print nlist[0:1000]
print "The amount of ZERO: ", nlist.count(0)
#print "Max ", max(nlist)
print "Len", len(primes)
count = 0

for i in range(2, 10**7-1):
    if nlist[i] == nlist[i+1]: 
	count += 1
	#print i, i+1
    #if nlist[i] == 0: print i

print count

print time.time() - now 
